package com.grape.dsaa.lineartable.stack.core;

import com.grape.dsaa.lineartable.stack.Stack;

import java.util.Arrays;
import java.util.EmptyStackException;
/**
 * 描述:数组实现栈
 * @author: myx
 * @date: 2019-04-28
 * Copyright © 2019-grape. All rights reserved.
 */
public class MyArrayStack<E> implements Stack<E> {
	private final static int DEFAULT_CAPACITY = 10;

	/**
	 * 保存栈元素的数组
	 */
	private E[] data;

	/**
	 * 栈中元素数量
	 */

	private int size;

	/**
	 * 栈顶索引
	 */
	private int top;
	
	public MyArrayStack(int capacity) {
		this.size = 0;
		this.top = -1;
		this.data = (E[]) new Object[capacity];
	}
	
	public MyArrayStack() {
		this(DEFAULT_CAPACITY);
	}
	
	@Override
	public boolean empty() {
 		return size == 0;
	}

	@Override
	public int size() {
 		return size;
	}

	@Override
	public void push(E item) {
		if(data.length == size) {
			grow(size * 2);
		}
		data[++top] = item;
		size++;
	}

	@Override
	public E pop() {
		if(size == 0) {
			throw new EmptyStackException();
		}
		
		size--;
		
		if(size < data.length/2) {
			grow(data.length/2);
		}
		
		return data[top--];
	}

	@Override
	public E peek() {
		if(size == 0) {
			throw new EmptyStackException();
		}	
		return data[top];
	}

	/**
	 * 动态扩容
	 * @param capacity
	 */
	private void grow(int capacity) {
		if(capacity <= DEFAULT_CAPACITY){
			return;
		}
		data = Arrays.copyOf(data, capacity);
	}
}